home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / amos / amoslist-0295.lzh / AMOSLIST / text0059.txt < prev    next >
Encoding:
Text File  |  1995-03-01  |  2.2 KB  |  87 lines
  1. On Tue, 31 Jan 1995, Flint wrote:
  2.  
  3. [...]
  4. > 
  5. > How does recursive programming work? 
  6. >
  7.  
  8.     Basically many problems can be solved by having some subtask call
  9.   itself as part of the sol'n.  This is recursion, ie. programs that call
  10.   themselves are recursive programs.  Why use recursion ?  Some recursive
  11.   solutions can be very short and simple compared to other iterative
  12.   solutions.  As an example consider the problem of a 'Flooding' Algorithm.
  13.   You know the 'paint' command in Amos (Note: Amos uses the OS to do its
  14.   flooding).  You can code it many different ways, and most use some
  15.   explicit use of some stack, but the simplest and most elegant (subjective)
  16.   is just to use recursion.  The disadvantage is that this simple method
  17.   is less effecient.  Here is an simple recursive algorithm for flooding
  18.    ar area: (pseudo Amos :) )
  19.  
  20.  
  21.     procedure Flood( x , y , color )
  22.  
  23.         if( Point(x,y) <> color ) 
  24.  
  25.             Ink color : Plot x,y
  26.  
  27.             Flood( x+1 , y   , color )
  28.             Flood( x-1 , y   , color )
  29.             Flood( x   , y+1 , color )
  30.             Flood( x   , y-1 , color )
  31.  
  32.         end if
  33.  
  34.     end proc
  35.  
  36.  
  37.    This works, by calling itslef on the 4 neighbouring pixels around
  38.    the pixel (x,y).  You just have to call it the first time with the
  39.    start pixel (x,y).
  40.  
  41. > Suppose I wanted to make a 
  42. > MineSweeper clone, how would I let the computer show all the fields 
  43. > that aren't surrounded by a bomb whenever I hit a field which is not 
  44. > surrounded by a bomb? 
  45. > Mind, I'm not trying to make a clone here, I just thought it's the best 
  46. > way to illustrate whatever I try to... well, er, try, really :)
  47. > 
  48.  
  49.     This is very much like the 'Flood' algorirthm above ( coincedence 
  50.   :) )...
  51.  
  52.  
  53.     Procedure Show_Mines( mine_x , mine_y )
  54.  
  55.         if( Number_of_Mines( mine_x, mine_y ) = 0 )
  56.             ' surrounded by no mines
  57.             
  58.             ' do whatever code you have to do to
  59.             ' actually show that this mine co-ordinate (x,y)
  60.             ' has actually been turned up/tested/etc...
  61.  
  62.             For y = -1 to 1
  63.                 For x = -1 to 1
  64.                   if( x<>0 and y<>0) 
  65.                       Show_Mines( mine_x + x , mine_y + y ) 
  66.                   endif
  67.                 Next
  68.             Next
  69.  
  70.         end if
  71.     end procedure
  72.  
  73.  
  74.  
  75.     I hope this helps...
  76.  
  77.                         Michael Sikorsky..
  78.  
  79. > Flint.
  80. > 
  81. > 
  82. > "My boy, if ever you are lost at sea, drop right in and think of me."
  83. > - J. Heller
  84. > 
  85. > 
  86.  
  87.